package com.faxon.leetcode.k;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Faxon
 * @version 1.0
 * @date 2020-04-21 16:19
 * 101. 对称二叉树
 * 给定一个二叉树，检查它是否是镜像对称的。
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 * 1
 * / \
 * 2   2
 * / \ / \
 * 3  4 4  3
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 * <p>
 * 1
 * / \
 * 2   2
 * \   \
 * 3    3
 * 进阶：
 * 你可以运用递归和迭代两种方法解决这个问题吗？
 **/
public class LeetCode101 {
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return recursiveCompare(root.left, root.right);
    }

    /**
     * 递归求解
     *
     * @param p
     * @param q
     * @return
     */
    public boolean recursiveCompare(TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            return q == p;
        }
        if (p.val != q.val) {
            return false;
        }
        return recursiveCompare(p.left, q.right) && recursiveCompare(p.right, q.left);
    }

    /**
     * 迭代求解
     *
     * @return
     */
    public boolean iterateCompare(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode p = queue.poll();
            TreeNode q = queue.poll();
            if (p == null || q == null) {
                if (q != p) {
                    return false;
                } else {
                    continue;
                }
            }
            if (q.val != p.val) {
                return false;
            }
            queue.add(p.left);
            queue.add(q.right);
            queue.add(p.right);
            queue.add(q.left);
        }
        return true;
    }

    @Test
    public void testIsSymmetric() {
        /*
         *         1
         *     /      \
         *    2        2
         *   / \      / \
         *  3   4    4   3
         * / \ / \  / \ / \
         * 1 2 2 3  3 2 2 1
         */
        TreeNode root = new TreeNode(1);
        TreeNode left1 = new TreeNode(2);
        TreeNode right1 = new TreeNode(2);
        root.left = left1;
        root.right = right1;
        TreeNode left2 = new TreeNode(3);
        TreeNode left3 = new TreeNode(4);
    }
}
